package com.leetcode.algorithm.y22.m06;

/**
 * 1049. 最后一块石头的重量 II
 * 
 * https://leetcode.cn/problems/last-stone-weight-ii/
 * 
 * @author jie.deng
 *
 */
class Question1049Solution01 {

	public int lastStoneWeightII(int[] stones) {
		int len = stones.length;
		int sum = 0;
		for (int i = 0; i < len; i++) {
			sum += stones[i];
		}

		// dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于j
		boolean[][] dp = new boolean[len][sum + 1];

		// 初始化状态
		dp[0][0] = true;
		dp[0][stones[0]] = true;

		for (int i = 1; i < len; i++) {
			int num = stones[i];
			for (int j = 0; j <= sum; j++) {
				if (dp[i - 1][j]) {
					dp[i][j] = true;
					dp[i][j + num] = true;
				}
			}
		}

		int diff = 0;
		int mid = sum >> 1;
		while (diff <= mid && !(dp[len - 1][mid + diff] || dp[len - 1][mid - diff])) {
			diff++;
		}
		if (dp[len - 1][mid + diff]) {
			return Math.abs(sum - (mid + diff) - (mid + diff));
		}
		return Math.abs(sum - (mid - diff) - (mid - diff));
	}

}